/*
 License
 
 Copyright © 2012 Kevin Kimmich
 
 Permission is hereby granted, free of charge, to any person obtaining a copy
 of this software and associated documentation files (the "Software"), to deal
 in the Software without restriction, including without limitation the rights to 
 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
 the Software, and to permit persons to whom the Software is furnished to do so, 
 subject to the following conditions:
 
 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
 INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
 PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
 FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "crcore.h"
#include "list.h"
#include "hashtable.h"

/**
 Private hashtable structure.
 */
struct bucket_node_t
{
	list_node_t node;
	uint32_t key;
	void* stringkey;
	uint32_t keylen;
	void* value;
};

//Thomas Wang's Hash Function
//http://www.concentric.net/~ttwang/tech/inthash.htm
//The link provides a really good overview of how a hash function ought to work.
static inline uint32_t hash32shiftmult(uint32_t key)
{
	const uint32_t c2=0x27d4eb2d; // a prime or an odd constant
	key = (key ^ 61) ^ (key >> 16);
	key = key + (key << 3);
	key = key ^ (key >> 4);
	key = key * c2;
	key = key ^ (key >> 15);
	return key;
}

//this is the ELF hash function (Used in ELF files)
static inline uint32_t hashstring(char *name, int len)
{
	uint32_t h = 0, g;
	char* p = name;
	while ( (p-name) < len ) {
		h = ( h << 4 ) + *p++;
		if ( (g = h & 0xF0000000) )
			h ^= g >> 24;
		h &= ~g;
	}
	return h;
}

//32 bit hash support functions
static uint32_t hash32bitkey( uint32_t mask, void* key, uint32_t keylen )
{
	uint32_t h = hash32shiftmult( *((uint32_t*)key) );
	h &= mask;
	return h;
}

static int compare_uint32( bucket_node_t* node1, void* key, uint32_t keylen )
{
	uint32_t* a = (uint32_t*)key;
	return node1->key - (*a);
}

static void assign_uint32( bucket_node_t* node, void* key, uint32_t keylen )
{
	node->key = *((uint32_t*)key);
}


//string hash support
static uint32_t hashstringkey( uint32_t mask, void* key, uint32_t keylen )
{
	uint32_t h = hashstring((char*)key,keylen);
	h &= mask;
	return h;
}

static int compare_string( bucket_node_t* node1, void* key, uint32_t keylen )
{
	if(node1->keylen != keylen)
		return -1;
	
	return memcmp(node1->stringkey,key,keylen);
}

static void assign_string( bucket_node_t* node, void* key, uint32_t keylen )
{
	node->keylen = keylen;
	node->stringkey = malloc(keylen);
	memcpy(node->stringkey,key,keylen);
}

static void cleanup_string( bucket_node_t* node )
{
	free(node->stringkey);
	node->stringkey=NULL;
}

//Public Functions

int hashtable_init( hashtable_t* h, hash_table_type_t type, uint32_t bucket_count )
{
	memset(h, 0, sizeof( hashtable_t ));
	
	uint32_t valid_count = ((bucket_count & (bucket_count-1))==0);//if bucket_count is not a power of two, this is false
	if(!valid_count)
		return -1;
	
	switch(type)
	{
		case HASHTABLE_UINT32:
			h->hash_func = hash32bitkey;
			h->key_compare = compare_uint32;
			h->key_assign = assign_uint32;
			h->key_cleanup = NULL;
			break;
		case HASHTABLE_STRING:
			h->hash_func = hashstringkey;
			h->key_compare = compare_string;
			h->key_assign = assign_string;
			h->key_cleanup = cleanup_string;
			break;
		default:
			printf("UNKNOWN HASH TYPE %d\n",type);
			exit(-1);
			break;
	};
	
	h->buckets = (list_t*) calloc( sizeof( list_t) , bucket_count );
	
	int i;
	for(i=0;i<bucket_count;i++)
		list_init(&h->buckets[i]);
	
	h->mask = bucket_count - 1;
	
	if(h->buckets)
	{
		pthread_mutex_init( &h->mutex, NULL );
		h->bucket_count = bucket_count;
		return 0;
	}
	
	return -1;
}

void hashtable_cleanup( hashtable_t* h, void(*callback)(void*) )
{
	pthread_mutex_lock( &h->mutex );
	
	int i;
	for(i=0;i<h->bucket_count;i++)
	{		
		list_node_t* pos;
		while(list_count(&h->buckets[i]))
		{
			pos = h->buckets[i].head.next;
			list_remove(&h->buckets[i], pos);
			bucket_node_t* node = (bucket_node_t*) pos;
			if(callback)
				callback(node->value);
			if(h->key_cleanup)
				h->key_cleanup(node);
			free(node);
		}
	}
	
	if(h->buckets)
		free(h->buckets);
	
	memset(h,0,sizeof(hashtable_t));
	
	pthread_mutex_unlock( &h->mutex );
}

static bucket_node_t* __lookup_node( hashtable_t* h, void* key, uint32_t keylen, uint32_t idx )
{
	list_node_t* pos;
	for(pos = h->buckets[idx].head.next; pos; pos = pos->next)
	{
		bucket_node_t* node = (bucket_node_t*)pos;
		if(h->key_compare(node,key,keylen)==0)
		{
			return node;
		}
	}
	return NULL;
}

int hashtable_insert( hashtable_t* h, void* key, uint32_t keylen, void* value )
{
	pthread_mutex_lock( &h->mutex );
	uint32_t idx = h->hash_func( h->mask, key, keylen );
	list_node_t* pos;
	for(pos = h->buckets[idx].head.next; pos; pos = pos->next)
	{
		bucket_node_t* node = (bucket_node_t*)pos;
		if(h->key_compare(node,key,keylen)==0)
		{
			pthread_mutex_unlock(&h->mutex);
			return -1;
		}
	}
	bucket_node_t* node = (bucket_node_t*) calloc(sizeof(bucket_node_t),1);
	h->key_assign(node,key,keylen);
	node->value = value;
	list_add_tail(&h->buckets[idx],&node->node);
	
	h->nodes_added++;
	
	pthread_mutex_unlock(&h->mutex);
	return 0;
}

int hashtable_delete( hashtable_t* h, void* key, uint32_t keylen, void** value )
{
	pthread_mutex_lock( &h->mutex );
	uint32_t idx = h->hash_func( h->mask, key, keylen );
	bucket_node_t* node = __lookup_node( h, key, keylen, idx );
	if(!node)
	{
		if(value)
			*value = NULL;
		pthread_mutex_unlock(&h->mutex);
		return -1;
	}
	if(value)
		*value = node->value;
	list_remove(&h->buckets[idx],&node->node);
	if(h->key_cleanup)
		h->key_cleanup(node);
	free(node);
	
	h->nodes_added--;
	
	pthread_mutex_unlock(&h->mutex);
	return 0;
}

int hashtable_lookup( hashtable_t* h, void* key, uint32_t keylen, void** value )
{
	pthread_mutex_lock( &h->mutex );
	uint32_t idx = h->hash_func( h->mask, key, keylen );
	bucket_node_t* node = __lookup_node( h, key, keylen, idx );
	if(!node)
	{
		if(value)
			*value = NULL;
		pthread_mutex_unlock(&h->mutex);
		return -1;
	}
	if(value)
		*value = node->value;
	pthread_mutex_unlock(&h->mutex);
	return 0;
}

int hashtable_count( hashtable_t* h )
{
	return h->nodes_added;
}
